As is known in the art, modern medical technology provides different modalities for acquiring 3D data, such as computed tomography (“CT”), magnetic resonance imaging (“MRI”), positron emission tomography (“PET”), and ultrasound. The information obtained from different modalities is usually complementary; for example, CT provides structural information while PET provides functional information. Thus, it is generally desirable to fuse multiple volumetric datasets.
FIG. 1 presents a sample-fused image where functional data from PET is correlated with structural information from CT. FIG. 1 shows a sample fused rendering. The image on the left (FIG. 1(a)) shows structural information derived from a 512×512×512×12-bit CT dataset, while the image in the center (FIG. 1(b)) shows functional information derived from a 256×256×256×16-bit dataset PET dataset. The image on the right (FIG. 1(c)) is a simple fusion of the CT and PET datasets correlating structural and functional information. The “negatives” of each of the images is shown to facilitate printed reproduction.
Most existing fusion renderers require that all volumes be aligned and have the same resolution, thereby necessitating that all volumes be re-sampled except the one that is treated as the reference volume. The reference volume generally refers to the volume with the finest resolution to avoid losing information—the other volumes are re-sampled according to the grid of the reference volume. The reference volume may need to be expanded to fill the bounding box enclosing all volumes. The aggregate bounding box of the ensemble of volumes can be significantly larger than individual bounding boxes when the orientation of a volume happens to lie near the diagonal of another volume. The number of voxels after re-sampling is proportional to the volume of the aggregate bounding box. Therefore, re-sampling can significantly increase the processing time (both initially and for each rendering) as well as the amount of memory required.
The volumes usually need to be registered because different scanners can have different coordinate systems (in terms of origins and orientations). During registration all volumes, except the reference volume, are referred to as floating volumes. Various transformations, such as rotation, translation, scaling, and shearing, are applied to the floating volumes so that their features match those in the reference volume. Furthermore, re-sampling must be performed again after such a transformation. Registration typically requires user interaction, with visual feedback, that is repeatedly applied to refine the registration. The resample-based fusion render cannot response quickly enough for such requirements.
Bricking is an important technique in texture-based volume rendering. In principle, bricking partitions a volumetric dataset into multiple sub-volumes, each called a brick. The purpose of bricking mainly falls to two. 1) Bricks containing only invisible voxels are skipped to gain acceleration; 2) Volumes larger than graphics memory can be rendered by downloading a subset of all the bricks to graphics memory for each rendering pass. With multiple rendering passes, all the visible voxels are processed. Within each brick, voxels can be further subdivided into blocks, and invisible blocks are skipped. Therefore, the minimal granularity of rendering is block, while the minimal granularity of texture downloading is brick. Obviously, a block has to be completely enclosed in the corresponding brick. See Wei Li, “Invisible Space Skipping with Adaptive Granularity for Texture-based Volume Rendering”, Published U.S. Patent Application Pub. No. 2006/0164410 published Jul. 27, 2006 assigned to the same assignee as the present invention, the entire subject matter being incorporated herein by reference, for more details about bricking.
A fusion renderer handles multiple volumes that usually overlap in 3D space. As discussed in co-pending U.S. patent application Ser. No. 11/235,410 filed Sep. 26, 2005, assigned to the same assignee as the present invention, the subject matter thereof being incorporated herein by reference. The basic idea described in U.S. patent application Ser. No. 11/235,410 is to render a whole slice through all blocks, hence performing the rendering in slice-by-slice order, instead of block-by-block. Briefly, the method includes the steps of: (a) building a hierarchical structure for each of a plurality of volumes; (b) finding all blocks in each of the hierarchical structures that intersect a slicing plane; (c) dividing each of the plurality of volumes into stacks of parallel slices and sorting the parallel slices by visibility order; (d) choosing a next slice in the sorted parallel slices, the next slice belonging to a current volume; (e) changing rendering parameters if the current volume is different from a previous volume in a previous iteration of step (d); (f) rendering, based on the rendering parameters, the next slice by intersecting the slicing plane with the blocks corresponding to the current volume; and (g) repeating steps (d)-(f) until all of the sorted parallel slices are rendered. It is desirable to keep each volume independent, rather than resampling them to the same resolution. Each volume maintains its own space-skipping structure. This has the advantage in rendering speed, memory consumption, and flexibility.
When a dataset is partitioned into bricks, not all voxels are accessible during a rendering pass. Therefore, an algorithm combining bricking and fusion have to guarantee that those inaccessible voxels are not rendered for the current pass, and any visible voxels are rendered exactly once. It is a challenging task, especially when invisible bricks and blocks are skipped. For simplicity, the previous co-pending U.S. patent application Ser. No. 11/235,410 only handles a simplified bricking scheme. That is, a volume is only bricked along the Z axis. In other words, each brick has at most two neighbors.
Bricking only in Z results in slab-shaped bricks, which unfortunately is less efficient in performance. Besides due to graphics hardware limitation, dataset whose X and Y sizes exceeding certain number, currently it is 512, cannot be rendered. Graphics memory is a precious resource in a system.
In accordance with the present invention, a method is provided for combining at least two three-dimensional image data sets to generate a composite image from the data sets. The method includes dividing each one of the data sets into a plurality of bricks along three mutually orthogonal axes. With such method, there is greater flexibility in selecting the shape/size of bricks resulting in better performance.
In one embodiment, a method is provided for combining at least two three-dimensional image data sets to generate a composite image from the data sets. The method includes: (a) building a hierarchical structure for each one of the at least two data sets, each hierarchical structure comprising higher level blocks of voxels of the data set thereof and lower level blocks of voxels of the data set thereof, the higher level blocks having a larger number of voxels than the lower level blocks, wherein one or more blocks occupy a single one of a plurality of initial processing bricks; (b) expanding boundaries of each one of the structures into corresponding expanded hierarchical structures, such boundary expanding comprising adding additional virtual processing bricks to the initial processing bricks, such virtual processing bricks comprising semi-unbounded blocks to provide the expanded boundaries of the expanded hierarchical structures; and (c) rendering each one of the bricks in each one of the expanded hierarchical structures into a two dimension image, such rendering.
With such method, each volume (i.e., data set) is expanded into a block tree having expanded nodes, so that the tree covers the whole 3D space, instead of limited by the bounding box of the volume. Rendering using the expanded tree guarantees that the rendering won't miss any portion of any volume. The expanded nodes are just virtual nodes that don't contain any voxel data.
In one embodiment, the rendering comprises: (i) processing the bricks each one of the expanded hierarchical structures in order of relative visibility, such visibility order being related to distance from a viewing camera including setting flags for invisible ones of the initial processing bricks and for the virtual processing bricks with visible bricks remaining un-flagged and wherein at any time a current brick is being rendered, cut planes defining the boundary the current brick being inserted and wherein the cut planes are removed when the current brick is no longer being rendered; (ii) dividing each of the expanded hierarchical structures having therein the current un-flagged brick into stacks of parallel slices along the cut planes with flagged bricks being excluded from the parallel slices and sorting the parallel slices by the visibility order; (iii) choosing a next slice in the sorted parallel slices, the next slice belonging to a currently rendered one of the bricks; (iv) finding all blocks in each of the currently bricks intersecting a plane of the next slice chosen in the (iii); (v) fetching voxels from the founds blocks; (vi) rendering the fetched voxels into the two dimensional image; (vi) repeating (iii) through (v) until all of the sorted parallel slices are rendered; and (vii) resetting the current brick.
Combined with the cut planes, the method guarantees that any visible portion of any volume is rendered exactly once.
In one embodiment, the parallel slices are chosen independently for each of the expanded hierarchical structures to render interleaved slices.
In one embodiment, the parallel slices are of the expanded hierarchical structures are chosen to share a common set of the parallel slices to generate fused slices; the invisible flags are passed to the rendering function, so that fetching from an invisible brick is avoid and 0 is assigned as the value of voxel sample. Samples fetched from different datasets are combined according to a customizable fusion equation, i.e., the equation depends on the real application. For example, it could be just average, sum, difference, or any other way of combining the voxel values fetched from the same 3D location of different volumes.
In accordance with the present invention, a common graphics memory manager and cache are shared among multiple GPU-based renderers as described in co-pending U.S. patent application Ser. No. 11/679,990 filed Feb. 28, 2007 assigned to the same assignee as the present invention, the subject matter thereof being incorporated herein by reference. To avoid the issue of memory segmentation, it is favorable that every renderer uses the same brick size. Consequently, bricking in all the three axes is necessary.
While in patent application Ser. No. 11/235,410 referred to above, different volumes are always treated independently (i.e., it does not sample different volumes at the same 3D locations and voxels samples from different volumes are not available at the same time inside a shader program), in some scenario, this feature is required. In such a mode, the brick-based renderer must ensure the accessibility of the required voxels from all the volumes for the current rendering pass, and each sampling location in 3D space is used only once throughout the rendering of the whole frame of image.
In this invention, expanded tree deployed by the fusion renderer of interleaving slices is used; here the shader program has access to the brick visibility flags. One way is to pass the brick visibility flags as arguments to the shader. If the current brick of a volume is invisible, the shader simply avoids sampling the volume, and assigns a zero to the variable holding the sampled value, and continues the fusion computation. This needs branches inside the shader program, and may not be efficient on some GPUs. Another way is to generate multiple versions of the shader program, each corresponding to a different subset of invisible volumes. The correct shader program is then selected depending on the brick visibility flags.
Invisible space skipping inside a brick for fused slices is different from rendering of interleaving slices. For interleaving slices, the renderer takes multiple sets of polygons that represent the sampling locations. Each set of polygons covers all the visible voxels of a volume. For fused slices, there is only one set of polygons that should cover all the visible voxels from all the volumes. Using the expanded nodes ensures the coverage of the space outside any volume. Inside a volume, if a brick if invisible, it is not just skipped, but introduces necessary cut-planes, and set the brick visibility flag to false for the related volume. For rendering fused slices, invisible blocks inside a brick is handled similarly by inserting cut-planes and setting brick visibility flag.
Like reference symbols in the various drawings indicate like elements.